Search for: All records

Let $Z^n$ be iid $$\text{Ber}(\delta)$$ and $U^n$ be uniform on the set of all binary vectors of weight $$\delta n$$ (Hamming sphere). As is well known, the entropies of $Z^n$ and $U^n$ are within $$O(\log n)$$. However, if $X^n$ is another binary random variable independent of $Z^n$ and $U^n$, we show that $H(X^n+U^n)$ and $H(X^n+Z^n)$ are within $$O(\sqrt{n})$$ and this estimate is tight. The bound is shown via coupling method. Tightness follows from the observation that the channels $$x^n\mapsto x^n+U^n$$ and $$x^n\mapsto x^n+Z^n$$ have similar capacities, but the former has zero dispersion. Finally, we show that despite the $$\sqrt{n}$$ slack in general, the Mrs. Gerber Lemma for $H(X^n+U^n)$ holds with only an $$O(\log n)$$ correction compared to its brethren for $H(X^n+Z^n)$. 

Two problems, namely multiple-description source coding and joint source-channel broadcasting of a common source, are addressed. For the multiple-description problem, we revisit Ozarow’s technique for establishing impossibility results, and extend it to general sources and distortion measures. For the problem of sending a source over a broadcast channel, we revisit the bounding technique of Reznik, Feder and Zamir, and extend it to general sources, distortion measures and broadcast channels. Although the obtained bounds do not improve over existing results in the literature, they are relatively easy to evaluate, and their derivation reveals the similarities between the two bounding techniques. 

Consider a binary linear code of length N, minimum distance dmin, transmission over the binary erasure channel with parameter 0 <  < 1 or the binary symmetric channel with parameter 0 <  < 1 2 , and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions “quickly” from δ to 1−δ for any δ > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/ √ dmin). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as Θ(1/N 1 2 −κ ), for any κ > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since Θ(1/N 1 2 ) is the smallest transition possible for any code, we speak of “almost” optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma. 

We consider an uncoordinated Gaussian multiple access channel with a relatively large number of active users within each block. A low complexity coding scheme is proposed, which is based on a combination of compute-and-forward and coding for a binary adder channel. For a wide regime of parameters of practical interest, the energy-per-bit required by each user in the proposed scheme is significantly smaller than that required by popular solutions such as slotted-ALOHA and treating interference as noise.